This invention relates to the process of call set-up in internet telephony. More particularly, the invention relates to procedures for determining how to interconnect the software switches that handle call set-up.
In conventional telephony, the analog voice signals that are the substance of telephone calls are delivered through a network of cables and switches referred to as the bearer network. By way of illustration, FIG. 1 shows a pair of telephones 10, 15, each connected to bearer network 20 through a respective local exchange switch 25, 30 which is, for example, a Lucent Technologies 5ESS switch. To establish a switched circuit between telephones 10 and 15 for the duration of the call, signaling messages are sent through a parallel, physical network of Signal Transfer Points (STPs). This parallel network, shown in FIG. 1 as network 35, is referred to as the signaling network. The establishment of a switched circuit is one type of call setup; specifically, it is the type of call setup performed in circuit-switched networks such as traditional telephone networks. It is a long-established requirement in conventional telephony that with 99% probability, call setup must be completed in time for a customer to hear a ring within two seconds after dialing. The actual time interval before a ring is heard is referred to as Post-Dialing Delay (PDD).
A newer kind of telephony, referred to as internet telephony, is rapidly growing in importance. In internet telephony, the substance of the telephone call is transmitted through a network of internet routers in the form of packetized signals which conform, e.g., to the TCP/IP protocol. Such a network of internet routers, referred to below as, simply, xe2x80x9cthe internet,xe2x80x9d is indicated in the figure as network 40. In internet telephony, call setup involves the establishment of an IP session instead of a switched circuit. To set-up a call, signalling messages are sent through a parallel network of software switches, such as Lucent Technologies Softswitches. A software switch network is indicated in FIG. 1 as network 45. In current implementations of internet telephony, the software switches of network 45 do not intercommunicate exclusively through dedicated hardware. Instead, they use the resources of the internet itself for intercommunication. Thus, unlike the physical signaling network of conventional telephony, the software switch of internet telephony (in current implementations) is a virtual network.
Like conventional telephony, internet telephony honors the 99% probability, two-second limit on PDD.
When a customer wishes to place an internet telephone call, he includes in the dialed number a string, referred to as a prefix, indicative of a particular provider of internet telephone service. Such a prefix typically consists of a seven-digit string included just before the seven-digit local telephone number being dialed. Thus, to the customer, the internet prefix is analogous to the seven-digit access code for long-distance carriers.
The internet prefix is interpreted at the originating local exchange switch, e.g., switch 25. In response, the call is sent to the internet and not to the conventional telephone network. As shown in FIG. 1, switch 25 sends call data directly to software switch network 45, and also to an associated Packet Voice Gateway (PVG) 50. As explained below, the PVG, in turn, sends data to internet router network 40 and to software switch network 45. Similarly, the local exchange switch at the receiving end, e.g., switch 30, receives data directly from network 45 and from an associated PVG 55. PVG 55 receives data from network 40 and from network 45. Finally, switch 30 connects to telephone 15.
Further information about the flow of signals is illustrated in FIG. 2. Elements common to FIGS. 1 and 2 bear the same reference numerals in both figures. Analog signals, represented in the figure by solid lines, flow between each telephone 10, 15 and the corresponding local exchange switch 25, 30. Analog signals also flow between each local exchange switch and a corresponding PVG 50, 55. Included among the functions of the PVG is analog-to-packet conversion. Accordingly, packet signals embodying the substance of the telephone call, represented in the figure by broken lines, flow between PVGs 50, 55 and the internet IP routers. Shown in the figure are the origination router, e.g., router 60, and the destination router, e.g., router 65.
Signaling messages, represented in the figure by dotted lines, pass among the multiple switches of the software switch network. Shown in the figure are origination and destination software switches 70 and 75. Also shown are two intermediate software switches 80 and 85. Origination software switch 70 also exchanges signaling messages with origination local exchange switch 25 and with origination PVG 50. Destination software switch 75 also exchanges signaling messages with destination local exchange switch 30 and with destination PVG 55.
Further details of the software switches are shown in FIG. 3. Elements common to FIGS. 2 and 3 bear the same reference numerals in both figures. Each software switch includes a plurality of Call Coordinators (CCs)100 and a Device Server (DS), such as an SS7 device server. Shown in the figure are DS 90, associated with orgination software switch 70, and DS 95, associated with destination software switch 75. For simplicity of presentation, the device servers associated with the intermediate software switches are not shown in the figure.
Among its other functions, the DS within each software switch processes the call set-up strings when that switch is the origination or destination switch for a call. The CCs set up the origin and destination PVGs. The DS also performs round-robin scheduling or other load-balancing operations among the various CCs of that switch. Thus, each CC within an individual switch communicates with the DS of that switch. However, the CCs within an individual switch do not typically communicate directly with each other.
Each CC of a given software switch is desirably connected to one or more CCs of one or more other switches, such that collectively, the interconnections among all of the CCs span the entire software switch network. That is, the network should be able to transmit set-up data for a call originating at any given software switch to any other software switch via a series of hops from switch to switch through the network.
A typical world-wide network for internet telephony may have as many as 200 or more software switches. Typically, each software switch will have several tens of CCs, exemplarily about 50 CCs. Thus, even with the constraint that CCs within an individual switch do not intercommunicate, the number of possible network designs is extremely large.
An advantageous network design should satisfy certain further requirements. For example, each hop consumes some time, which may be as much as 100 ms or more. If excessive delay accumulates during a transit of the network, call set-up may not be achieved in time to satisfy the two-second limit on PDD. Therefore, it is desirable for the diameter of the network, i.e., the number of hops separating the most distant pair of CCs, to be limited to a small number, such as two hops.
Typically, the links between CCs are virtual links. Under TCP/IP and certain other protocols, for example, these links are of the kind referred to as sockets. As will be appreciated by those skilled in the art, a socket is a software construct that permits communication between computational processes. A disadvantageous property of sockets in software switches is that for each CC, delay and overhead penalties increase with the number of open sockets belonging to such CC. The delay and overhead penalties are not proportional to the number of open sockets, but instead have a rate of increase that is faster than proportionality. Thus, a second desirable feature of a CC network is that the number of links ending on a given CC (i.e., the degree of that CC) should be relatively small.
The respective requirements of small network diameter and of small degree are difficult to satisfy simultaneously, because a degree limitation inherently limits the number of short paths (i.e., paths of one or two hops) available between arbitrarily selected CC pairs.
In principle, a computational aide to designing an advantageous CC network is available in the form, for example, of an Integer Program. By solving an Integer Program, it is possible to generate a network that conforms to the stated requirements. However, the computational complexity of such a solution grows exponentially in the total number of CCs in the network. Thus, for all but very small networks, it is intractable to solve an IP at reasonable time and expense.
Thus, there has been lacking, until now, a practical method for designing a CC network of arbitrary size that satisfies the desired limitations on network diameter and on CC degree.
We have discovered a practical method for designing a CC network of arbitrary size that satisfies, with high probability, limitations on network diameter and on CC degree. In a broad aspect, our invention involves treating the network of CCs, initially, as a collection of isolated points, one point for each CC. Then, links are added between pairs of CCs, excluding fraternal pairs, i.e., pairs lying within the same switch. The links are added randomly, but with a particular probability p, which may be different for different pairs. That is, between each admissible pair (i.e., each pair not lying within the same switch), a link is either added or not added. Whether the link is added depends, in effect, upon the outcome of a loaded coin toss, in which the probability of a positive outcome is p.
We have been able to prove, mathematically, that when p assumes appropriate values, it is highly tractable to find, among alternative networks generated as described above, a network of diameter 2 whose maximum degree is substantially less than the total number n of CCs in the network. For example, with a probability that approaches 1 as n increases, no more than 2 ln n alternative networks need to be generated and searched in order to find a network of diameter 2 and maximum degree {square root over (2.1n(ln n))}.
In fact, in numerical simulations, we have found that as a general rule, the first network to be generated is satisfactory as to diameter and maximum degree.
In specific embodiments of the invention, the random network that has been constructed is improved further in a post-processing step. In the post-processing step, links are added between those admissible pairs that are still separated by more than two hops. The further links are added until all admissible pairs are connected by at most two hops.
Accordingly, the invention in one aspect involves performing, at least once, a step of randomly assigning edges to pairs of vertices of a graph wherein each vertex represents a node of the communication network. The random assignment is carried out such that: (i) any fraternal pair has zero probability of being assigned an edge, but all admissible pairs have a finite probability of being assigned an edge; and (ii) at least one resulting graph, denominated a low-degree graph, has a maximum degree less than 2{square root over (n(nl n))}. The invention further includes adding edges, if any are needed, to a low-degree graph until all admissible vertex pairs of the resulting graph are connected by a path of at most two edges. The invention further includes mapping vertices of the resulting graph to nodes of the communication network.